package com.agile.leetcode.middle.reorderedPowerOf2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给定正整数 N ，我们按任何顺序（包括原始顺序）将数字重新排序，注意其前导数字不能为零。
 * <p>
 * 如果我们可以通过上述方式得到 2 的幂，返回 true；否则，返回 false。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：1
 * 输出：true
 * 示例 2：
 * <p>
 * 输入：10
 * 输出：false
 * 示例 3：
 * <p>
 * 输入：16
 * 输出：true
 * 示例 4：
 * <p>
 * 输入：24
 * 输出：false
 * 示例 5：
 * <p>
 * 输入：46
 * 输出：true
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/reordered-power-of-2
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author:ChenZhangKun
 * @Date: 2021/3/17 16:20
 */
public class ReorderedPowerOf2 {
    public static void main(String[] args) {
        ReorderedPowerOf2 reorderedPowerOf2 = new ReorderedPowerOf2();
        System.out.println(reorderedPowerOf2.reorderedPowerOf2_1(155));
    }

    public boolean reorderedPowerOf2(int N) {
        // 拿到数字的长度
        int numLength = (N + "").length();
        // 创建集合存储各个数
        List<Integer> list = new ArrayList<>(10);
        int j = 10;
        for (int i = 0; i < numLength; i++) {
            int mod = N % j;
            list.add(mod);
            N = N / 10;
            j *= 10;
        }
        return true;
    }

    /**
     * 官方死路解法
     *
     * @param N
     * @return
     */
    public boolean reorderedPowerOf2_1(int N) {
        int[] count = count(N);
        // 枚举所有2的幂
        for (int i = 0; i < 31; i++) {
            // 对位数进行对比
            if (Arrays.equals(count, count(1 << i))) return true;
        }
        return false;
    }

    public int[] count(int N) {
        // 创建数字个数统计数组
        int[] arr = new int[10];
        // 创建数组
        do {
            int mod = N % 10;
            N = N / 10;
            arr[mod]++;
        } while (N != 0);
        return arr;
    }
}
